package com.leetcode.search.bfs;

import java.util.*;
import java.util.stream.Collectors;

/**
 * @author Dennis Li
 * @date 2020/8/2 16:52
 */
public class OpenLock_752 {

    public int openLock(String[] deadends, String target) {
        Set<Integer> deads = Arrays.stream(deadends)
                .map(Integer::valueOf).collect(Collectors.toSet());
        Set<Integer> visited = new HashSet<>();
        // 将字符串转换为整型进行计算
        int t = Integer.parseInt(target);
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(0);
        visited.add(0);
        // 记录走过的节点
        int depth = 0;
        while (!queue.isEmpty()) {
            // 必须要把size提出来，放到for循环里面会导致queue.size()动态更新，陷入无限循环
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int num = queue.poll();
                // 如果包含在了死锁中，那么不再从这个结点出发遍历
                if (deads.contains(num)) continue;
                // 找到结果，返回当前的深度
                if (num == t) return depth;
                // j代表位置
                for (int j = 0; j < 4; j++) {
                    // 分别将向上拨数字和向下记录
                    int plusOne = plusOne(num, j);
                    int downOne = downOne(num, j);
                    // 确保不走回头路
                    if (!visited.contains(plusOne)) {
                        queue.offer(plusOne);
                        visited.add(plusOne);
                    }
                    if (!visited.contains(downOne)) {
                        queue.offer(downOne);
                        visited.add(downOne);
                    }
                }
            }
            // 记录当前纵深 -- 看成一棵树
            depth++;
        }
        return -1;
    }

    // 拨数字盘的方法实现
    public int plusOne(int num, int j) {
        int exp = (int) Math.pow(10, j);
        return num / exp % 10 == 9 ? num - exp * 9 : num + exp;
    }

    public int downOne(int num, int j) {
        int exp = (int) Math.pow(10, j);
        return num / exp % 10 == 0 ? num + exp * 9 : num - exp;
    }

    // 双向BFS
    // 必须要同时知道起点和终点才可以
    public int openLock2(String[] deadends, String target) {
        Set<Integer> deads = new HashSet<>();
        for (String s : deadends) deads.add(Integer.valueOf(s));
        // 用集合不用队列，可以快速判断元素是否存在
        Set<Integer> q1 = new HashSet<>();
        Set<Integer> q2 = new HashSet<>();
        Set<Integer> visited = new HashSet<>();

        int step = 0;
        q1.add(0);
        q2.add(Integer.valueOf(target));

        while (!q1.isEmpty() && !q2.isEmpty()) {
            // 哈希集合在遍历的过程中不能修改，用 temp 存储扩散结果
            // 并且可以不保存之前的节点
            Set<Integer> temp = new HashSet<>();

            /* 将 q1 中的所有节点向周围扩散 */
            for (int cur : q1) {
                /* 判断是否到达终点 */
                if (deads.contains(cur))
                    continue;
                if (q2.contains(cur))
                    return step;
                visited.add(cur);

                /* 将一个节点的未遍历相邻节点加入集合 */
                for (int j = 0; j < 4; j++) {
                    int up = plusOne(cur, j);
                    if (!visited.contains(up))
                        temp.add(up);
                    int down = downOne(cur, j);
                    if (!visited.contains(down))
                        temp.add(down);
                }
            }
            /* 在这里增加步数 */
            // step最终相当于层的抬升，双向BFS主要是会将上层和下层进行交换再执行抬升，可以减少一些点的遍历
            step++;
            // temp 相当于 q1
            // 这里交换 q1 q2，下一轮 while 就是扩散 q2
            q1 = q2;
            q2 = temp;
        }
        return -1;
    }

    static class Solution {
        public int openLock(String[] deadends, String target) {
            Set<Integer> deads = Arrays.stream(deadends)
                    .map(Integer::valueOf).collect(Collectors.toSet());
            Set<Integer> set = new HashSet<>();
            int tar = Integer.parseInt(target);
            Queue<Integer> queue = new LinkedList<>();
            queue.offer(0);
            set.add(0);
            int times = 0;
            while (!queue.isEmpty()) {
                int size = queue.size();
                while (size-- > 0) {
                    int node = queue.poll();
                    if (deads.contains(node)) continue;
                    if (node == tar) return times;
                    for (int i = 0; i < 4; i++) {
                        int plus = plusOne(node, i), minus = minusOne(node, i);
                        if (!set.contains(plus)) {
                            queue.offer(plus);
                            // 在这里就添加，保证不会被重复访问，不然每次依然会访问大量重复结点
                            set.add(plus);
                        }
                        if (!set.contains(minus)) {
                            queue.offer(minus);
                            set.add(minus);
                        }
                    }
                }
                times++;
            }
            return -1;
        }

        public int plusOne(int num, int i) {
            int exp = (int) Math.pow(10, i);
            int temp = (num / exp) % 10;
            return temp == 9 ? (num - 9 * exp) : (num + exp);
        }

        public int minusOne(int num, int i) {
            int exp = (int) Math.pow(10, i);
            int temp = (num / exp) % 10;
            return temp == 0 ? (num + 9 * exp) : (num - exp);
        }

        public int openLock2(String[] deadends, String target) {
            Set<Integer> deads = Arrays.stream(deadends).parallel()
                    .map(Integer::valueOf).collect(Collectors.toSet());
            Set<Integer> q1 = new HashSet<>(), q2 = new HashSet<>(), visited = new HashSet<>();
            q1.add(0);
            q2.add(Integer.valueOf(target));
            int times = 0;
            while (!q1.isEmpty() || !q2.isEmpty()) {
                // 用临时集合实现调换 -- 可以剔除上一层的节点
                Set<Integer> set = new HashSet<>();
                for (int num : q1) {
                    if (deads.contains(num)) continue;
                    if (q2.contains(num)) return times;
                    visited.add(num);
                    for (int i = 0; i < 4; i++) {
                        int plus = plusOne(num, i), minus = minusOne(num, i);
                        if (!visited.contains(plus))
                            set.add(plus);
                        if (!visited.contains(minus))
                            set.add(minus);
                    }
                }
                times++;
                q1 = q2;
                q2 = set;
            }
            return -1;
        }
    }

}


